Here is a question that sounds like a children's riddle. Which is bigger: the set of all counting numbers (1, 2, 3, …) or the set of just the even ones (2, 4, 6, …)? The evens are obviously half of the counting numbers. And yet, by the only fair way mathematicians have found to compare infinite collections, the two are exactly the same size.
Then comes the twist that made the 19th century uneasy. Some infinite collections really are bigger than others. Not "a bit bigger". Bigger in a way that no amount of cleverness can repair. This piece walks you to that edge, and the interactive below lets you perform the proof with your own hands.
Imagine a café before anyone learned to count. Is the number of cups the same as the number of saucers? You don't need numbers to find out. Put one cup on each saucer. If nothing is left over on either side, the two collections are the same size.
That pairing idea, a one-to-one correspondence, is what Georg Cantor used in the 1870s to compare infinite sets. Two sets are the same size if you can pair their members off perfectly, with nobody left out on either side. Apply it to the evens:
| Counting number | 1 | 2 | 3 | 4 | 5 | … | n |
|---|---|---|---|---|---|---|---|
| Even number | 2 | 4 | 6 | 8 | 10 | … | 2n |
Every counting number gets exactly one even partner, and every even number is somebody's partner. Nothing is left over, so the sets are the same size. In finite sets a part is always smaller than the whole. In infinite ones a part can be as big as the whole. That property is so characteristic of infinity that it can serve as a definition of "infinite".
David Hilbert made this vivid with an imaginary hotel. He used it in a lecture in Göttingen in January 1924, though his text went unpublished until 2013. The physicist George Gamow made it famous in a 1947 book. The hotel has infinitely many rooms, numbered 1, 2, 3, …, and every one is taken.
A traveller arrives. No problem: the manager asks every guest to move from room n to room n + 1. Everyone still has a room, and room 1 is now free. Then a coach pulls up with infinitely many new guests. Still no problem: everyone moves from room n to room 2n. The current guests now fill the even rooms, and every odd room is empty for the newcomers.
Even fractions fit. Write all fractions in a grid (top number across, bottom number down) and walk the short diagonals one at a time, skipping repeats like 2/2: 1/1, then 1/2, 2/1, then 1/3, 3/1, then 1/4, 2/3, 3/2, 4/1, and so on. Every positive fraction appears somewhere on that walk, so the fractions can be given room numbers too. Any set you can list like this, first, second, third, forever, is called countable.
At this point it looks as if every infinity is the same infinity. It isn't.
Now take all the decimals between 0 and 1: 0.5, 0.333…, 0.14159…, every one of them. Suppose someone claims to have listed them all, a first, a second, a third and so on forever. Cantor showed how to build, from any such list, a number that cannot be on it.
The recipe: look at the 1st digit of the 1st number, the 2nd digit of the 2nd number, the 3rd digit of the 3rd, and so on down the diagonal. Build a new number by changing every one of those digits. (Here the rule is: if the digit is 5, write 4; otherwise write 5.) The new number differs from the 1st number in the 1st place, from the 2nd number in the 2nd place, from every number on the list somewhere. So it isn't on the list. The list was not complete after all.
Below is the beginning of a list that claims to contain every decimal. Tap any digit to change it and try to sabotage the method, then build the escape number one digit at a time.
Try "Add it to the list". The patched list is longer, but the diagonal simply runs one step further and produces a fresh escape number. You can patch forever; the method beats every patch, because it beats every possible list. So the decimals between 0 and 1 cannot be listed at all. They form a strictly bigger infinity than the counting numbers. Mathematicians call the counting-number size ℵ0 ("aleph-null") and say the decimals are uncountable.
Why only 4s and 5s? Some numbers have two decimal spellings: 0.4999… equals 0.5000…. A rule that wrote 0s or 9s could, in principle, build a different spelling of a number already on the list. Using only 4 and 5 sidesteps that loophole.
The version above is the textbook one. Cantor's first proof that the real numbers can't be listed, published in 1874, used a different method (nested intervals). His famous diagonal paper of 1891 applied the idea to infinite sequences of two symbols rather than to decimals; translating it into decimals came later. The idea is his; the classroom packaging is everybody's.
The 1891 paper went further. Cantor showed that for any set, the collection of all its subsets is strictly bigger than the set itself. Apply that to the decimals and you get a bigger infinity. Apply it again and you get a bigger one still. There is no largest infinity. There is an endless ladder of them, each one dwarfing the last.
Infinity isn't a place you arrive at. It's a staircase that never stops going up.
Cantor then asked the obvious next question. Is there an infinity between the counting numbers and the decimals? He believed not. That guess is the continuum hypothesis, and he spent years trying to prove it.
The answer, when it came, was stranger than yes or no. In 1940 Kurt Gödel showed that the standard axioms of set theory (the rules nearly all of mathematics is built on) can't disprove the hypothesis. In 1963 Paul Cohen invented a technique called forcing and showed that the same axioms can't prove it either. It is independent of them. Cohen received the Fields Medal in 1966 for the work. A perfectly clear question about sizes of infinity turns out to be undecidable from the rules we use. (For the wider story of questions like this, see Gödel's Incompleteness Theorems.)
Cantor paid a price for this. Leopold Kronecker, one of the most powerful mathematicians in Germany, attacked his work, and Henri Poincaré was sceptical. Cantor suffered repeated episodes of depression, often linked to these attacks (though historians now suspect an underlying illness the criticism made worse). He was hospitalised several times and died in a psychiatric clinic in Halle in January 1918.
The mathematicians who came after him took his side. In a 1925 address, published in 1926, Hilbert declared: "No one shall expel us from the paradise that Cantor has created." Today set theory is the foundation the rest of mathematics is built on.
Two infinite sets are the same size when their members can be paired off perfectly. By that test the evens, the whole numbers and even all the fractions are the same size, the "countable" infinity. The decimals are not: Cantor's diagonal argument builds, from any list of them, a number the list missed, so they form a strictly larger infinity. Above that sits an endless tower of ever-larger infinities, and whether anything sits between the first two rungs (the continuum hypothesis) can be neither proved nor disproved from mathematics' standard rules.
Try this: explain Hilbert's Hotel to someone at dinner. First have one guest arrive, then infinitely many. Then ask them how the manager could fit in one guest for every decimal between 0 and 1. (He can't. Now you know why.)
Sources. Cantor's 1874 uncountability proof (Crelle's Journal, vol. 77) and 1891 diagonal paper (Jahresbericht der DMV, vol. 1), and the power-set theorem, are standard history of set theory. Hilbert's hotel: H. Kragh, "The True (?) Story of Hilbert's Infinite Hotel" (2014), on the January 1924 lecture, its 2013 publication and Gamow's 1947 popularisation. Gödel (1940) and Cohen (1963–64, PNAS) on the independence of the continuum hypothesis; Cohen's 1966 Fields Medal (Britannica). Cantor's illness and Kronecker's opposition: MacTutor and the Wikipedia biography. Hilbert's "paradise" line: "Über das Unendliche", Mathematische Annalen 95 (1926), from a 1925 address. The interactive's escape number was checked in node against thousands of random lists: it always differs from row k at digit k.